수송망은 상품, 데이터 또는 물질이 제한된 통로를 통해 이동하는 것을 모델링하기 위해 사용되는 전문적인 수학적 구조입니다. 표준 방향 그래프를 특정 출발점과 도착점으로 지정함으로써 기능적인 틀로 변환하며, 시스템 내 모든 연결에 물리적인 '병목' 한계를 부과합니다.
수송망의 정의
정의 10.1.1에 따르면 정의 10.1.1수송망(또는 간단히 네트워크라고 함)은 세 가지 핵심 조건을 만족해야 하는 단순한 가중치가 있는 방향 그래프입니다:
성질 (a): 원천
지정된 정점인 원천 ($a$ 또는 $s$)는 출발점입니다. 들어오는 간선이 없으며(입도 = 0), 무한한 공급원 역할을 합니다.
성질 (b): 종착지
지정된 정점인 종착지 ($z$ 또는 $t$)는 최종 소비자를 나타냅니다. 나가는 간선이 없으며(출도 = 0).
성질 (c): 용량
각 방향 간선 $(i, j)$의 가중치 $C_{ij}$는 그 용량이라고 하며, 반드시 음수가 아닌 수($C_{ij} \geq 0$)여야 하며, 간선이 지원할 수 있는 최대 흐름을 나타냅니다.
실제 사례 비유: 지역 전력망
이 추상적인 개념들을 실제 생활에 적용해 보세요. 지역 전력망을 생각해 보세요:
- 원천: 거대한 수력 발전소. 전기를 생산만 하며, 그리드에서 전기가 발전소로 들어오지 않습니다.
- 종착지: 중공업 중심지. 들어오는 모든 전기를 기계를 작동시키기 위해 소비하며, 그리드로는 아무것도 되돌려주지 않습니다.
- 간선과 용량: 송전선이 간선이며, 그 용량은 열에 의해 고장나기 전까지 물리적 와이어가 견딜 수 있는 최대 전류입니다.
- 중간 정점: 흐름을 소비하지 않고 방향을 재지정하는 지역 변전소(흐름 보존 원칙).
용량과 흐름의 차이점
용량과 흐름을 구분하는 것은 매우 중요합니다 용량 와 흐름입니다. 용량 $C_{ij}$는 정적 물리적 성질이며, 잠재적인 부피입니다. 흐름 $F_{ij}$는 특정 순간에 실제로 이동하고 있는 부피입니다. 이 슬라이드에서는 구조적 제약 용량에만 집중하며 현재의 움직임 상태는 고려하지 않습니다.
🎯 핵심 원리: 구조적 제약
모든 수송망은 방향 그래프이며, 흐름은 공급원(원천)에서 소비자(종착지)로, 음수가 아닌 용량으로 제한된 통로를 통해 이동합니다.
원천: $deg^-(a) = 0 \quad | \quad$ 종착지: $deg^+(z) = 0 \quad | \quad$ 용량: $C_{ij} \geq 0